// 长度最小的子数组
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0;
        int len = INT_MAX, sum = 0;
        while (right < nums.size())
        {
            // 进窗口
            sum += nums[right];
            // 判断
            while (sum >= target)
            {
                // 更新结果
                len = min(len, right - left + 1);
                // 出窗口
                sum -= nums[left++];
            }
            right++;
                     
        }
        return len == INT_MAX ? 0 : len;
    }
};
// 无重复字符的最长子串--利用容器map
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0, right = 0, len = 0;
        map<char, int> map_count;
        while (right < s.size())
        {
            // 进窗口
            map_count[s[right]]++;
            // 判断 + 出窗口
            while (map_count[s[right]] >= 2)
            {
                map_count[s[left++]]--;
            }
            // 更新结果
            len = max(len, right - left + 1);
            right++;
        }
        return len;
    }
};
// 无重复字符的最长子串--利用数组充当哈希
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size() , count = 0;
        int haxi[128] = {0};
        for (int left = 0 , right = 0; right <= n -1; right++)
        {
            haxi[s[right]]++;
            while (haxi[s[right]] >= 2)
            {
                haxi[s[left++]]--;
            }
            count = max(count , right - left + 1);
        }
        return count;
    }
};
// 最大连续1的个数-无count变量
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int left = 0, right = 0, len = 0;
        while (right < nums.size())
        {
            // 判断
            while (nums[right] == 0)
            {
                // 出窗口
                if (nums[left++] == 0) break;
            }
            // 更新结果
            len = max(len, right - left + 1);
            right++;
        }
        return len;
    }
};
// 最大连续1的个数-用count变量来统计窗口中0的个数
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int left = 0, right = 0;
        int len = 0, count = 0;
        while (right < nums.size())
        {
            if (nums[right] == 0) count++;
            // 判断 + 出窗口
            while (count >= 1)
            {
                if (nums[left++] == 0) count--;
            }
            len = max(len, right - left + 1);
            right++;
        }
        return len;
    }
};
// 将x减到0的最小操作数
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        // 先计算出nums总数之和
        int sum = 0;
        for (auto& val : nums) sum += val;
        int target = sum - x;
        
        // 处理特殊情况
        if (target < 0) return -1;
        if (target == 0) return nums.size();
        
        int left = 0, right = 0, len = 0;
        int ret = 0; // 用变量ret去计算窗口总数的和
        while (right < nums.size())
        {
            ret += nums[right];// 进窗口
            while (ret >= target)
            {
                // 更新结果
                if (ret == target)
                {
                    len = max(len, right - left + 1);
                }              
                ret -= nums[left++];
            }
            right++;
        }
        return len == 0 ? -1 : nums.size() - len;
    }
};

// 水果成篮-利用容器map
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // 利用容器map进行求解
        map<int, int> count_map;
        int left = 0, right = 0;
        int count = 0, len = 0;
        while (right < fruits.size())
        {
            count_map[fruits[right]]++; // 进窗口
            if (count_map[fruits[right]] == 1) count++;
            while (count > 2) // 判断 + 出窗口
            {
                if (count_map[fruits[left]] == 1)
                    count--;
                count_map[fruits[left++]]--;
            }
            len = max(len, right - left + 1); // 更新结果
            right++;
        }
        return len;
    }
};
// 利用哈希数组
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001] = {0};
        int n = fruits.size() , kind = 0;
        int len = 0;
        for (int left = 0 , right = 0; right <= n - 1; right++)
        {
            hash[fruits[right]]++;//进窗口
            if (hash[fruits[right]] == 1) kind++;
            while (kind > 2)
            {
                if (hash[fruits[left]] == 1) kind--;
                hash[fruits[left]]--;
                left++;
            }
            len = max(len , right - left + 1);
        }
        return len;
    }
};

// 找到字符串中所有单词的异位词
class Solution {
    bool compare(map<char, int>& p1, map<char, int>& p2)
    {
        for(auto& [k, v] : p1)
        {
            if (v != p2[k])
                return false;
        }
        return true;
    }
public:
    vector<int> findAnagrams(string s, string p) {
        map<char, int> s_map;
        map<char, int> p_map;
        for(auto& ch : p) p_map[ch]++;
        int left = 0, right = 0;
        vector<int> ret;
        while (right < s.size())
        {
            s_map[s[right]]++;// 进窗口
            if (right - left + 1 == p.size()) // 出窗口
            {
                if (compare(s_map, p_map))
                    ret.push_back(left); // 更新结果
                s_map[s[left++]]--;
            }
            right++;
        }
        return ret;
    }
};

// 问题代码
class Solution {
    bool compare(const map<char, int>& p1, const map<char, int>& p2)
    {
        for(auto& [k, v] : p1)
        {
            if (p2.find(k) == p2.end())
                return false;
            else
            {
                if (v != p2.at(k))
                    return false;
            }
        }
        return true;
    }
public:
    vector<int> findAnagrams(string s, string p) {
        map<char, int> s_map, p_map;
        for(auto& ch : p) p_map[ch]++;
        int left = 0, right = 0;
        vector<int> ret;
        while (right < s.size())
        {
            s_map[s[right]]++;// 进窗口
            if (right - left + 1 == p.size()) // 出窗口
            {
                if (compare(s_map, p_map))
                    ret.push_back(left); // 更新结果
                s_map[s[left++]]--;
            }
            right++;
        }
        return ret;
    }
};

// 找出字符串中所有单词的异位词-哈希数组
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        // 用哈希数组去模拟map
        int hasi1[128] = {0};
        int hasi2[128] = {0};
        // 先将p中字符输入到hasi2中
        int kind = 0; // 变量kind用来统计p中有效字符的个数
        for (auto& ch : p)
        {
            hasi2[ch]++;
            if (hasi2[ch] == 1) kind++;
        }
        vector<int> ret;
        int count = 0, left = 0, right = 0;
        while (right < s.size())
        {
            hasi1[s[right]]++;
            if (hasi1[s[right]] == hasi2[s[right]])
                count++;
            if (right - left + 1 == p.size())
            {
                if (count == kind) ret.push_back(left);
                if (hasi1[s[left]] == hasi2[s[left]]) count--;
                hasi1[s[left++]]--;   
            }
            right++;
        }
        return ret;
    }
};

// 最小覆盖子串
class Solution {
public:
    string minWindow(string s, string t) {
        // 利用哈希进行求解
        int hash1[128] = {0};
        int hash2[128] = {0};
        
        // 将t中的字符输入到hash2中，并维护kind的值
        int kind = 0;
        for(auto& ch : t)
        {
            hash2[ch]++;
            if (hash2[ch] == 1) kind++;
        }
        // 直接定义五个变量，为滑动窗口做准备
        int left = 0, right = 0;
        int count = 0, len = INT_MAX, start = 0;
        while (right < s.size())
        {
            // 进窗口 + 维护count
            hash1[s[right]]++;
            if (hash1[s[right]] == hash2[s[right]]) count++;
            while (count == kind)
            {
                // 更新结果
                if (right - left + 1 < len)
                {
                    len = right - left + 1;
                    start = left;
                }
                // 维护count + 出窗口
                if (hash1[s[left]] == hash2[s[left]]) count--;
                hash1[s[left++]]--;
            }
            right++;
        }
        if (len == INT_MAX) return "";
        else return s.substr(start, len);
    }
};
// 最小覆盖子串--利用容器map的加强版本
class Solution {
public:
    string minWindow(string s, string t) {
        map<char, int> s_map;
        map<char, int> p_map;
        int kind = 0;
        for (auto& ch : t)
        {
            p_map[ch]++;
            if (p_map[ch] == 1) kind++;
        }
        
        int left = 0, right = 0;
        int count = 0, len = INT_MAX, start = 0;
        while (right < s.size())
        {
            if (p_map.find(s[right]) != p_map.end()) 
            {
                s_map[s[right]]++;
                if (s_map[s[right]] == p_map[s[right]]) count++;
            }
            while (count == kind)
            {
                if (right - left + 1 < len)
                {
                    len = right - left + 1;
                    start = left;
                }
                
                if (p_map.find(s[left]) != p_map.end())
                {
                    if (s_map[s[left]] == p_map[s[left]]) count--;
                    s_map[s[left++]]--;
                } 
                else left++;
            }
            right++;
        }
        if (len == INT_MAX) return "";
        else return s.substr(start, len);
    }
};